package leetcode.L500;

public class EX34 {
    static class Solution {
        public static void main(String[] args) {
            int[] nums = {2,2};
            int t = 3;
            searchRange(nums,t);
        }

        public static int[] searchRange(int[] nums, int target) {
            int[] fa = {-1,-1};
            if(nums.length==0){
                return fa;
            }
            int[] res = new int [2];
            res[0] = first(nums,target);
            if(res[0]==-1){
                return fa;
            }
            res[1] = end(nums,target);
            return res;
        }

        public static  int first(int[] nums, int target){
            int left = 0;
            int right = nums.length;
            int mid = 0;

            while(left<right){
                mid = left+(right-left)/2;
                if(nums[mid]==target){
                    right = mid;
                }
                else if(nums[mid]>target){
                    right = mid;
                }
                else{
                    left = mid+1;
                }

            }
            if(nums[left]!=target){
                return -1;
            }
            return left;
        }

        public static int end(int[] nums, int target){
            int left = 0;
            int right = nums.length;
            int mid = 0;

            while(left<right){
                mid = left+(right-left)/2;
                if(nums[mid]==target){
                    left = mid+1;
                }
                else if(nums[mid]>target){
                    right = mid;
                }
                else{
                    left = mid+1;
                }
                if(nums[left-1]!=target){
                    return -1;
                }

            }
            return left-1;
        }

    }
}
